package com.itzmn.newcode.offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/15 14:26
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 剑指Offer，从上到下打印数节点
 *
 *  层序遍历需要借助队列，打印当前节点，但是要将左右子节点如队列；
 *
 *  层序遍历
 *         1
 *       2   3
 *     4  5
 *
 */
public class PrintTreeTopToBottom {

    public static void main(String[] args) {

        new PrintTreeTopToBottom().init();
    }
    public void init(){

        int[] ints = {1, 2, 3, 4, 5};
        TreeNode tree = createTree(ints);
        cengxu(tree);
    }


    public void cengxu(TreeNode root){

        //借助队列
        LinkedList treeNodes = new LinkedList<>();
        treeNodes.add(root);

        while (!treeNodes.isEmpty()){
           TreeNode treeNode = (TreeNode) treeNodes.remove();
           ArrayList<Integer> integers = new ArrayList<>();
           integers.add(treeNode.val);
           System.out.println(treeNode.val);
           if (treeNode.left != null){
               treeNodes.add(treeNode.left);
           }
           if (treeNode.right != null){
               treeNodes.add(treeNode.right);
           }
       }
    }

    /**
     * 根据数组创建二叉树
     * @param arrs
     * @return
     */
    public TreeNode createTree(int[] arrs){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int i:arrs){
            treeNodes.add(new TreeNode(i));
        }
        TreeNode root = treeNodes.get(0);

        for (int i = 0; i < arrs.length/2; i++) {
            if (i*2+1<arrs.length){
                treeNodes.get(i).left=treeNodes.get(i*2+1);
            }
            if(i*2+2<treeNodes.size()){//避免偶数的时候 下标越界
                treeNodes.get(i).right=treeNodes.get(i*2+2);
            }
        }

        return root;

    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
